package q670_maximumSwap;

public class Solution {
    /*
    题目中给出的数字之多只有8位 因此不需要考虑数字溢出的问题
    并且可以直接使用暴力解法：将其转化为数组，然后每两个位置都交换一次，维护一个最大值，每次发现一个更大的就更新
    最后能够得到结果
    为了降低时间复杂度，这里可以使用贪心的方法：
    我们期望的是对于一个位置，其右侧有一个最大值位置maxIdx才去尝试交换 例如 1 2 3 肯定是交换1和3比较大
    所以可以从最后一个位置开始遍历，如果发现了更大的值就更新maxIdx，否则我们每次都能够记录一个idx1和idx2
    也就是我们期望交换的左侧一个位置和右侧它所发现的最大maxIdx
    注意如果arr[i] = arr[maxIdx]时是不做任何操作的
    例如1993和98368
     */
    public int maximumSwap(int num) {
        char[] arr = String.valueOf(num).toCharArray();
        int maxIdx = arr.length - 1;
        int idx_1 = -1, idx_2 = -1;
        for (int i = arr.length - 1; i >= 0; --i) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            } else if (arr[i] < arr[maxIdx]) {
                idx_1 = i;
                idx_2 = maxIdx;
            }
        }
        if (idx_1 >= 0) {
            swap(arr, idx_1, idx_2);
            return Integer.parseInt(new String(arr));
        } else {
            return num;
        }
    }
    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
